Here we transform our sequence of matched gadget blocks to an injectable binary string.  We call this process \textit{resolution}, and it is performed in three stages: \textit{lib(c) resolution}, \textit{pointer resolution} and \textit{offset resolution}.  Each resolution stage may add more gadget blocks to the sequence, which will necessitate more gadget assignment.  We refer to the original set of gadget blocks as the \textit{payload proper}, since these perform the actions the attacker had in mind.  Additional gadget blocks from the resolution process are prepended to the payload sequence as the \textit{prologue}.  The prologue may be regarded as a series of configurations which must be performed at run-time before the payload proper is entered.
\subsection{lib(c) resolution}
\label{sec:resolution:libc}
Our application allows gadgets to be used from both the vulnerable binary and lib(c)\footnote{While for simplicity our software only supports lib(c), these techniques will work with any shared library.}.  To leverage lib(c) gadgets, we must address the following problems:
\begin{enumerate}
\item lib(c) is dynamically linked and may not be loaded at exploit-time.
\item lib(c) is mapped to an unpredictable location.
\end{enumerate}
We ignore issue 1 by assuming lib(c) is loaded at exploit-time\footnote{Alternatively, a dynamic loading of lib(c) may be forced by jumping to \verb+F@plt+, where \verb+F+ is a harmless lib(c) function used by the vulnerable binary.}.  This is a well-grounded assumption, since our attack string was mostly likely moved into memory with a lib(c) utility (e.g., \texttt{strcpy}, \texttt{memcpy}).  Issue 2 remains, however, since we require the global addresses of the lib(c) gadgets in order for ROP to work.  Our solution is drawn from \cite{surgically}:
\begin{enumerate}
\item Choose an arbitrary function $F$ in lib(c) which is called by the vulnerable program.
\item Obtain the relative address of $F$, $F_d$ within lib(c)\footnote{This can be obtained with \verb+objdump -d libc-x.yy.so+.}.
\item For each lib(c) gadget appearing in our payload, set the gadget address to the relative address of the gadget in lib(c).
\end{enumerate}
These steps are all computed prior to runtime.  During the exploit, lib(c)'s base address is resolved, then all the lib(c) gadget addresses are resolved:
\begin{enumerate}
\item Examine the Global Offset Table (GOT) entry for $F$ to obtain $F$'s address $A_{F}$\footnote{This can be obtained with \verb+objdump -D ./vuln_bin+.}.
\item Obtain the base address of lib(c): $A_{lib(c)} = A_{F} - F_d$
\item For each gadget, add to the gadget address $A_{lib(c)}$.
\end{enumerate}
This procedure will yield the resolved lib(c) gadget addresses.  The lower steps are the first to be executed in the payload prologue.  It should be mentioned that the gadgets performing these steps must not reside in lib(c).  Figure~\ref{fig:libc_resolution_1} contains a concrete example.  Note that the raw addresses drawn in the frames have already been converted to little-endian order.

lib(c) resolution is the last phase requiring access to the original gadget blocks.  Henceforth, we treat each gadget block as a raw stack item containing the gadget address followed by a sequence of stack items \footnote{We are only considering 32-bit architectures for now.} and dispense with the gadget block structures. That is, lib(c) resolution concludes with a resolution of \textit{gadget blocks} to \textit{sequences of stack items}.
\begin{figure}
\hspace{2em}
\begin{drawstack}[scale=0.85]
  \cell{lib(c) base pointer} \cellcom{(populated with ptr)}
  \padding{1}{...payload...}
  \cell{(gadget pointer)} \cellcom{\texttt{mov [ECX], EAX; ret}}
  \cell{$p_{lib(c) base pointer}$}
  \cell{(gadget pointer)} \cellcom{\texttt{pop ECX; ret}}
  \cell{(gadget pointer)} \cellcom{\texttt{sub EAX, EBX; ret}}
  \cell{\texttt{0xb0de0d00}} \cellcom{(rel. address of \texttt{open()})}
  \cell{(gadget pointer)} \cellcom{\texttt{pop EBX; ret}}
  \cell{(gadget pointer)} \cellcom{\texttt{mov EAX, [ECX]; ret}}
  \cell{0x10a00408} \cellcom{(GOT addr of \texttt{open()})}
  \cell{(gadget pointer)} \cellcom{\texttt{pop ECX; ret}}
\end{drawstack}
\caption{lib(c) base address resolution.  We strive to load the base address of lib(c) into the field labeled ``lib(c) base pointer". We load the address of \texttt{open()}'s GOT entry (\texttt{0x0804a010}) into \texttt{ECX} and then dereference it into \texttt{EAX}.  Subtracting the relative address of \texttt{open()} in lib(c) (\texttt{0x000ddeb0}) gives lib(c)'s base address, which we write to the base pointer field via $p_{lib(c) base pointer}$.}
\label{fig:libc_resolution_1}
\end{figure}

\subsection{Pointer resolution}
\label{sec:resolution:pointer}
Now we must contend with \textit{pointer stack items}.  The purpose of these fields, to reiterate, is to allow for the construction of complicated data structures on the stack which are accessible to the payload at runtime.  However, we cannot know the value of any pointer at compile-time due to ASLR.  We present a technique for runtime pointer resolution, which works in the following way: Suppose we have a payload field $A$ at offset $d_A$ (from the start of the payload) and require a pointer to $A$, $p_A$, at offset $d_{p_A}$.  At compile-time, we put $d_A - d_{p_A}$ in $p$.  We then introduce a \textit{pointer resolver} in the payload prologue, which:
\begin{enumerate}
\item Obtains the current value of \texttt{ESP}, $S$.
\item Obtains the offset $D$ from itself to $p$ (known at compile-time).
\item Adds $D + S$ into $p$.
\end{enumerate}
Then $p$ contains the global address of $A$.  This procedure is shown in Figure~\ref{fig:pointer_resolution_1}.

Note that the stack item containing $D$ is storing an offset between the second gadget in the resolver and the stack pointer.  Furthermore, the stack pointer initially stores an offset between itself and $A$.  In \textit{R} we represent both fields with a \textit{offset stack items}.  Thus, pointer resolution can be regarded as a resolution from \textit{pointer stack items} to \textit{offset stack items}.

\begin{figure}
\hspace{-7em}
\begin{drawstack}[scale=0.85]
  \cell{$A$}
  \startframe
  \padding{1}{...payload...}
  \cell{$p_A$: $d_A - d_{p_A}$}
  \finishframe{$d_A - d_{p_A}$}
  \startframe
  \padding{1}{...payload...}
  \cell{(gadget pointer)} \cellcom{\texttt{add [EAX], EAX; ret}}
  \cell{(gadget pointer)} \cellcom{\texttt{add EAX, EBX; ret}}
  \cell{$D$}
  \cell{(gadget pointer)} \cellcom{\texttt{pop EBX; ret}}
  \finishframe{$D$}
  \cell{(gadget pointer)} \cellcom{\texttt{mov EAX, ESP; ret}}
\end{drawstack}
\caption{Stack pointer resolution.  We strive to load the global address of $A$ into $p_A$.  When the first gadget is executed (\texttt{mov EAX, ESP; ret}), \texttt{ESP} points to the second gadget.  Thus, adding $D$ to \texttt{ESP} gives the location of $p_A$, and $D + $ \texttt{ESP} $+ p_A$ gives the address of $A$. The instruction sequences shown are just examples; any functionally equivalent chunks will do.}
\label{fig:pointer_resolution_1}
\end{figure}

\newpage
\subsection{Offset resolution}
Offset resolution is the final resolution step.  To review, a \textit{offset stack item} is a type which records the distance between two labelled stack entities $A$ and $B$.  Resolving such an item to raw binary is straightforward: Starting from $A$, walk along the payload in the direction of $B$, adding the sizes of all stack items passed along the way\footnote{If $B$ is earlier than $A$ in the payload, the opposites of the sizes are added in order to yield a negative value.}.  When $B$ is reached, store this value in a new \textit{raw stack item} and substitute this item for the offset stack item.  In short, offset resolution is a resolution of \textit{offset stack items} to \textit{raw stack items}.  At this point, our entire payload consists of raw stack items.

\subsection{Payload printing}
Following offset resolution, we are left with merely a sequence of raw stack items.  Generating a binary payload involves only concatenating them together.

We wish to make clear that after the payload has been generated, the attacker must supply a way to appropriately place this payload in the victim process's memory.
